package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;

import utils.BracketUtils;

//设计LRU缓存
public class Nc93 {
    
    public class Solution {
        /**
         * lru design
         * @param operators int整型二维数组 the ops
         * @param k int整型 the k,容量
         * @return int整型一维数组
         * 若opt=1，接下来两个整数x, y，表示set(x, y)
           若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
         */
        
        public int[] LRU (int[][] operators, int k) {
            LRU lru = new LRU(k);
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < operators.length; i++) {
                if (operators[i][0] == 1) {
                    lru.put(operators[i][1], operators[i][2]);
                } else {
                    res.add(lru.get(operators[i][1]));
                }
            }

            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    class LRU {
        private int capacity;
        private Map<Integer, Node> map = new HashMap<>();
        private DoubleList dl = new DoubleList();

        public LRU(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                Node res = map.get(key);
                dl.removeToFirst(res);
                return res.val;
            } else {
                return -1;
            }
        }

        public void put(int key, int val) {
            if (map.containsKey(key)) {
                Node res = map.get(key);
                dl.removeToFirst(res);
                res.val = val;
            } else {
                if (dl.size() == capacity) {
                    int t = dl.removeLast();
                    map.remove(t);
                }
                Node cur = dl.insert(key, val);
                map.put(key, cur);
            }
        }


        class DoubleList {
            Node head, tail;

            int size;

            public DoubleList () {
                this.size = 0;
            }

            public int size() {
                return this.size;
            }

            public Node insert(int key, int val) {
                Node node = new Node(key, val);
                if (head == null) {
                    head = node;
                    head.prev = null;
                    tail = node;
                    tail.next = null;
                } else {
                    //新节点插入到队首
                    node.next = head;
                    head.prev = node;
                    head = node;
                    head.prev = null; //其实可以默认的
                }
                this.size++;
                return node;
            }

            public int removeLast() {
                Node prev = tail.prev;
                prev.next = null;
                tail.prev = null;
                int res = tail.key;
                tail = prev;
                this.size--;
                return res;
            }

            public void remove(Node node) {
                //移除某个节点
                Node next = head.next;
                if (next == null) {
                    head = null;
                    tail = null;
                } else if (node == head) {
                    head.next = null;
                    next.prev = null;
                    head = next;
                } else if (node == tail) {
                    Node prev = tail.prev;
                    prev.next = null;
                    tail.prev = null;
                    tail = prev;
                } else {
                    next.prev = node.prev;
                    node.prev.next = next;
                    node.next = null;
                    node.prev = null;                  
                }
            }

            public void removeToFirst(Node node) {
                remove(node);
                node.next = head;
                if (head != null) {
                    head.prev = node;
                }
                if (tail == null) {
                    tail = node;
                }
                head = node;
            }
        }
        class Node {
            int key;
            int val;
            Node next;
            Node prev;

            public Node(int key,int val) {
                this.key = key;
                this.val = val;
            }
        }
    }

    @Test
    public void test() {
        // int[][] nums = BracketUtils.to2DArray("[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]]");
        int[][] nums = BracketUtils.to2DArray("[[1,-324690837,-72487934],[1,-723504364,-369145172],[2,-324690837],[1,724101438,-30727452],[1,366967562,290286156],[2,366967562],[1,-21417066,-450706222],[1,-484359960,-121414361],[1,-629538923,-759874959],[1,-461538894,749719150],[1,-338664886,-3080586],[2,522415046],[1,134352387,-391032350],[1,283492390,210901529],[2,-328994470],[2,-254674447],[2,85161833],[1,36899859,-561167545],[1,-232060336,889831435],[1,-848557701,-189598178],[2,-81051921],[1,57162090,-193776405],[1,157908494,-941008658],[2,-21417066],[2,-485579587],[2,449908952],[1,12002448,-273547528],[1,-267371849,634867878],[1,128963067,102756157],[2,36899859],[2,145140817],[2,335181121],[1,89294557,-213039610],[2,204879021],[2,36899859],[2,-371773103],[1,-354568989,-788098655],[2,283492390],[2,148848181],[1,641416456,-646693824],[1,-970438681,341383327],[1,452656493,-68334619],[1,209021588,229415889],[1,580338695,-286744639],[1,263639066,-99669610],[1,-586507345,255143085],[2,89294557],[2,209021588],[1,888670782,-378802985],[1,-751520980,8161338],[2,12002448],[1,-967501590,-351688503],[2,514432065],[2,80361112],[1,220830017,-93263524],[2,32131049],[1,-264084048,-155050456],[1,-482193643,-232757642],[2,134352387],[1,-303458351,-974058471],[2,452656493],[1,505909889,-508809796],[1,28202319,577206570],[2,-991605984],[2,-266360965],[2,553306411],[1,-91084058,95483640],[1,141869753,-629556641],[1,-48119420,783684131],[1,610948343,6884450],[2,641416456],[1,-412360441,31222570],[1,431900251,231767188],[2,-588592923],[1,-220001478,-183147041],[2,-69417139],[2,-34241947],[1,396626603,-435781001],[2,161660462],[2,-788025808],[2,-622427224],[1,-18852505,647730929],[2,-978490],[1,-203099668,-173289604],[1,-9216750,-116999009],[2,241113210],[2,-586507345],[1,439742836,3892905],[1,362692206,64119965],[1,-343557119,25898321],[1,351163245,558921656],[2,220830017],[2,-139705440],[1,-63307654,582782467],[1,174271875,647087188],[1,-366938003,141242360],[2,225133310],[2,-49488568],[2,-303458351],[2,505909889],[2,-808960104],[2,396626603],[1,-26838658,-388178020],[2,-153211277],[2,-144774404],[1,-536064025,-36365386],[2,734467312],[2,220830017],[1,365062309,-318717846],[2,-324832567],[2,439742836],[1,-180868327,-159966095],[2,-751520980],[2,580338695],[2,-354568989],[2,-970438681],[2,26297015],[2,53336527],[2,362692206],[1,764975865,98827347],[2,580338695],[2,359090605],[1,173783545,18855798],[2,207679480],[2,-586507345],[2,-671308317],[1,-147481120,-236880874],[1,-450464797,-656448819],[2,-220001478],[2,458548499],[2,512481060],[1,-283224868,207900800],[1,532173329,52355843],[1,-194778332,84957035],[2,-696498893],[1,270980443,-201798815],[1,-284268265,-266052042],[1,683156246,-174712401],[2,-724220256],[2,-284978646],[2,-536034019],[2,-948025850],[1,500743456,-857564859],[2,-21417066],[2,-87644587],[1,-996330989,871353671],[2,209021588],[1,-155001207,26189758],[1,464264726,777669292],[1,901475284,580732539],[2,620408599],[2,-182346941],[1,77548279,377999221],[2,559663093],[2,-89893990],[1,-11398914,-79363115],[2,234604060],[1,58056122,898427066],[1,-476866252,-1050895013],[2,-476866252],[2,-970438681],[1,-49326594,-89296749],[1,2389948,56816865],[2,-573102964],[1,-216981304,206915595],[1,746634933,-612245610],[2,20576250],[2,856695302],[1,43169930,-390580889],[2,306842501],[2,-284268265],[2,301960693],[1,74683996,198134686],[1,832613060,-346486472],[2,-629538923],[2,-206577199],[1,-740500778,-143640401],[1,-3411096,-85869900],[2,446562789],[2,724101438],[2,-725031868],[1,286102301,-14510950],[2,-629538923],[2,-536064025],[2,115029095],[1,50391685,646291074],[1,-833285737,-106282103],[2,-220001478],[2,286102301],[1,-240968826,481665516],[1,-248654947,141473482],[2,84564331],[2,538570885],[1,-187773218,-122949130],[2,-19115532],[1,584981001,-39539798],[1,-16677395,-652359713],[2,98183776],[1,-170378496,569136991],[1,117709567,-118835073],[1,10032547,-139671520],[2,819646106],[1,-387536461,558731394],[1,410472328,353323519],[1,287174735,339213466],[2,57143769],[2,173783545],[2,141869753],[1,332013945,528944067],[2,-121908994],[1,-836135440,-124037743],[1,247903747,683827049],[1,-508933719,-380296894],[1,225249246,-167329495],[2,-689788876],[1,440399176,-340124586],[2,724101438],[2,366967562],[2,-751520980],[1,466525944,8739442],[1,32664730,-434238833],[1,420658486,-185496440],[2,-484359960],[1,131890805,-794313446],[1,-428948987,277877427],[1,234796684,242162300],[2,224883777],[2,-848557701],[1,-70344578,130581821],[2,34289428],[2,-179377895],[1,-240663072,-338383747],[1,45474024,521537939],[2,-736183951],[2,-330287655],[1,-154193909,560418666],[2,-538628046],[1,663784448,-298467067],[2,-996330989],[1,327390258,62138329],[2,-428948987],[1,-444507221,623739459],[1,316542353,-256860191],[2,-629538923],[1,-364879024,267242206],[1,209216464,-439699603],[2,506387476],[1,523833568,123210071],[1,294355661,-149778303],[2,333362885],[1,32676942,73053343],[1,641441535,229116580],[2,307185739],[1,265185612,-81811528],[1,405826161,-472216588],[2,-508933719],[1,-684343510,-79605436],[2,222918204],[2,-773734934],[2,-191450286],[2,888670782],[2,-112610749],[1,258190587,-248830756],[1,527788638,-354581783],[2,413722721],[1,-192027283,768504779],[2,-293151039],[2,-240363421],[1,-72558259,109141665],[2,99701623],[1,-43471846,800050314],[2,170784160],[2,-595931223],[1,-210873070,671248579],[2,-48119420],[1,-23607724,-751381211],[1,-857147854,448437654],[1,354606489,91180311],[1,119863179,-393523009],[2,57162090],[2,-37702629],[1,338685800,-182822424],[1,175133709,885476412],[2,114697206],[1,131120093,-555359446],[1,321945348,-222421900],[1,-155232318,217368474],[1,91704539,-681725994],[2,-49326594],[2,-799210091],[1,-950635679,-357265696],[2,-517832954],[2,463414303],[2,199804327],[2,-563166895],[1,-281445697,-269566182],[2,-151034596],[1,709624041,416432282],[1,-164695523,315079029],[1,-204165153,-843263134],[1,469989065,324300023],[2,5863562],[2,128963067],[2,328339075],[2,-746413574],[1,554716995,-214110538],[1,284924829,-121406947],[1,-471227514,-317598971],[2,-465052176],[2,-272403486],[1,-900429599,-61220555],[2,-832620948],[2,-130825851],[2,157908494],[1,-377918647,-259470648],[1,156372214,-33682724],[1,-333595881,38338566],[1,-236877115,443848807],[1,-368447786,17969814],[1,281659973,-337592229],[2,77548279],[2,-476866252],[1,280746444,120527303],[1,354393705,-569397459],[1,-28610579,356409797],[2,-2164992],[1,674527550,75173704],[1,142818255,490219818],[1,334697376,54011679],[1,533916322,-47581330],[1,275959783,468782044],[1,737310984,-635324190],[2,-157588071],[1,196023934,-372452604],[1,-117210176,-329937451],[1,461912915,516996739],[2,-474004659],[2,386062914],[1,-83022334,39062241],[2,-361168796],[1,-663601211,503990419],[2,-33914681],[1,-419989099,-656019478],[2,281659973],[2,350121324],[1,575301955,89632497],[1,-79351757,-477156624],[1,-700883727,-346809936],[1,385599659,36796228],[2,254297197],[1,-67083943,508236547],[1,-454701917,32732671],[1,669415341,-30394601],[1,-184876207,302282519],[2,-499223032],[1,772886717,-177086413],[2,28202319],[2,-375347119],[1,-275011157,3318538],[1,803084265,392960454],[2,-652643277],[2,-405333072],[2,-368447786],[2,396626603],[2,-740500778],[1,56822042,-119862250],[2,-324690837],[1,786164541,170039359],[2,205148022],[1,-63529672,168649305],[1,937267637,208478033],[2,-86718094],[1,825155456,602889653],[1,69578086,-121997008],[2,174271875],[2,268790554],[2,-188465991],[2,308516298],[2,-267371849],[1,145188540,240342343],[2,587565445],[2,937267637],[1,776765261,-7209454],[2,683171671],[2,469989065],[2,347507042],[2,234796684],[2,-117210176],[1,-459789422,-468572980],[2,-192027283],[1,-11809221,-468832993],[1,-156587421,61782243],[2,-23607724],[2,-281445697],[1,-277278876,-103088305],[2,28202319],[2,265185612],[1,348794011,-283890741],[2,-364879024],[2,-219848854],[2,70741186],[2,-72555900],[1,-611423410,-159352426],[2,-28610579],[1,533212182,-790445750],[1,-563506715,-180535647],[1,-636782508,-84423634],[2,800874231],[1,-285086434,328987839],[1,-343122272,-173845304],[1,636968133,-202933825],[1,-220566751,-135608612],[1,-752504350,-31069261],[1,131483652,-223204670],[1,72431491,-892330888],[2,-719216028],[2,351163245],[1,987278481,-234236881],[2,518259814],[2,-822157727],[1,142098336,-680823953],[2,768057958],[2,131890805],[2,365062309],[1,-7195282,-275364228],[2,-326676097],[2,-684343510],[2,110885531],[1,397003860,-752348244],[1,-115091187,-726122336],[1,-342557253,5992987],[1,-154758436,-19653405],[2,-418556409],[2,-21417066],[1,-842765913,328032691],[2,10645293],[1,132990648,304313149],[1,-715316529,-609386117],[2,39659200],[2,-684343510],[1,204704252,152221334],[2,-155232318],[2,74683996],[2,246011417],[2,-244829540],[2,428981902],[2,303262714],[2,32676942],[1,-467128457,-608223455],[2,142098336],[1,-675192573,895690828],[2,396626603],[1,509039658,-208240224],[1,-345974496,-119705984],[2,-467128457],[1,-347537925,-252740924],[2,-264084048],[1,-483071935,422294408],[2,-156587421],[2,-924764792],[1,-83862564,328812741],[1,-259044848,-316932567],[1,557261000,-724740030],[1,448721455,417434319],[2,580722735],[1,45738330,309857142],[2,-202134113],[2,123431289],[1,395360543,-123146951],[1,-367560219,-29859628],[2,764975865],[2,-232060336],[2,-413147472],[1,620634862,119804532],[2,-785474845],[2,62932816],[1,-749537463,-390606498],[2,-779132378],[1,53250961,817854598],[1,-78551401,330433619],[1,-1003638715,-337811816],[2,289999383],[2,95738855],[1,-454349917,-312172433],[2,-571775157],[2,-246717330],[1,45198175,-29485631],[1,-247809230,-454565301],[2,563868941],[2,-467801041],[1,-145580009,217811590],[2,-409335944],[2,258277112],[1,562946732,-143877562],[1,284227716,538544134],[1,477396415,152948633],[2,-437392907],[2,-186387362],[2,533916322],[1,306259930,479999725],[2,688747674],[2,386638062],[1,-544947306,-184388652],[1,-215594926,543981002],[1,233342423,127580234],[2,-117641028],[2,-616452804],[1,635438584,407175290],[1,-313651679,1036001606],[1,478351007,16948959],[2,455819291]" 
        +"[1,-352083247,-111624718],[1,-152903501,617013411],[1,24673794,-522946071],[2,-176608366],[1,-33250927,-332114483],[1,-127634926,257011811],[2,339651650],[2,323026226],[2,-147162196],[1,-337105455,-782021213],[1,524253595,-122202719],[1,-290501805,-437278077],[2,358618406],[2,769611172],[1,711020333,228082221],[2,-154193909],[1,97373085,248973451],[1,-566518183,-264783711],[2,-203099668],[1,528012866,520883303],[2,-127386140],[2,57158963],[1,773986253,375094615],[1,758363129,-504924839],[2,-155232318],[1,810084836,-57991090],[2,-192939844],[2,157999007],[2,208306752],[1,-838189646,-105902203],[1,8855173,301282302],[1,-213876500,93847328],[1,-297747172,-274752817],[2,-46317634],[2,182562227],[1,-548187157,-119665153],[1,-112997245,-78307511],[1,-770173983,392151318],[2,-467319814],[2,-343122272],[2,-164695523],[1,-313709513,24060014],[2,-833285737],[2,-444507221],[1,327977002,141017346],[1,-597349275,-733289275],[2,478351007],[2,44186254],[2,550780507],[1,846530515,-277038450],[2,383191125],[2,306259930],[1,-13837402,968948523],[1,98359196,109865709],[2,261635563],[1,-546211920,178603783],[1,494712967,321254740],[2,90926084],[2,1048904510],[1,799356468,3830891],[2,592875169],[1,-197237842,832589916],[1,93035630,-489152671],[1,618010474,750352577],[1,-246126710,196561533],[2,80730603],[1,-754811893,722194757],[2,-611423410],[1,-238697569,-424388772],[1,155368807,-69094687],[1,625568280,-272439773],[1,192071690,-487921341],[1,928140849,-388619029],[1,283314865,-350183927],[1,178897571,-638870989],[2,329039063],[1,-506157351,14041130],[2,752962939],[1,697994898,836788828],[1,135812477,-188187325],[1,801851645,475245442],[2,828116277],[1,88482048,-791056895],[1,594155811,-533872486],[1,-494942248,163593196],[2,-193330632],[2,354393705],[2,538211660],[2,-372631651],[1,-36581479,295074287],[1,-182032440,-298544876],[1,189108743,46791865],[2,206423817],[2,-364879024],[1,-170246983,550335973],[2,24673794],[1,396899955,83832233],[1,-149665358,-301611333],[2,495535767],[2,16382384],[1,-314224817,-363915788],[2,-301671963],[1,-215209920,-1016398160],[1,600282617,-1049349],[2,-529419070],[1,210228252,-584402812],[1,153288948,-173863175],[2,294136708],[1,-27556347,-172074951],[2,375680488],[2,899166513],[1,-716577145,-382932973],[1,191711511,53421033],[2,57009331],[2,-454701917],[2,-784742819],[1,-773829108,-160970684],[2,171959024],[1,-146027276,-119359233],[2,636968133],[1,-747309863,-81747513],[1,-123512122,261783314],[1,-313560183,-385846190],[2,731748955],[2,755992457],[1,-522086257,119560355],[1,-430575827,-103131865],[1,752953287,318903479],[2,19035523],[1,227719070,795774109],[1,221094149,-480825204],[1,265428066,-600218725],[1,-885331010,-427631715],[1,-122139809,-92026219],[2,-194094573],[2,746377639],[1,188286578,-244949621],[2,198237081],[2,-4747622],[2,-273195144],[1,-226167410,-277200923],[2,34246328],[1,205357731,553424296],[2,319015456],[2,462009837],[1,-710961341,177718499],[1,-682960479,342669164],[2,-482193643],[2,529539241],[2,-63307654],[2,127587080],[1,-316758295,776439022],[2,662221827],[1,-249599354,481620711],[2,191197192],[1,766143213,-284814199],[1,145489801,1061867267],[2,497495213],[1,361590213,-708519483],[2,487999035],[2,-403689334],[2,348794011],[2,-593931038],[2,184990267],[1,-44057115,-442441823],[2,-496271261],[1,-260850044,-216494566],[2,213034268],[2,579369847],[2,-13837402],[2,228539211],[2,-528620802],[2,-253389114],[1,246865207,-86172390],[2,45474024],[1,14027633,-288158420],[1,399955866,227771362],[2,-822766794],[2,-290659609],[1,-950195472,-228104138],[1,-117806067,409036630],[2,80908645],[2,-411274898],[2,-178770548],[1,-818747081,26319217],[1,-93413597,163824881],[1,-253947747,-895054106],[2,179764676],[2,-544947306],[2,-836135440],[2,411950087],[1,-751659426,-816174840],[2,-313709513],[2,-132138687],[1,193409052,735283230],[1,-521486215,-507891664],[1,-333552837,-184199080],[1,723008970,-417623152],[1,355145166,-603768611],[2,346884298],[1,-581006139,-244902730],[1,-64208635,-193106353],[1,-571591634,-26527086],[1,237003702,150061054],[2,527381174],[1,-66959748,-528047226],[2,398507451],[1,-644196599,-672001974],[1,-942731688,279803418],[2,-22827890],[2,-363525113],[1,-400577381,291741786],[2,-614489085],[1,-18980738,-81628081],[1,570717555,462940133],[2,-442252440],[2,410472328],[1,-1027126094,-33694968],[2,14027633],[2,-961567424],[2,-253588580],[2,246865207],[2,45198175],[2,-347537925],[1,-241313762,-76020785],[1,526271164,-644660920],[1,133764087,-2042203],[2,31545769],[2,-483442769],[1,-45799353,60804433],[1,-230394296,-664191526],[1,-188236722,-640189226],[1,277682593,25395348],[2,-317072077],[2,-20722438],[1,-745213021,-393428193],[1,-59694386,-474283744],[1,-286395658,413651617],[1,314779908,37399434],[1,682345507,-216343253],[1,-674767072,-649841605],[1,375831236,359441856],[2,-340395436],[1,276924078,888410837],[1,-826318570,-535261778],[1,436116242,-214638547],[2,178467901],[2,-276568770],[2,175733796],[2,549338026],[1,-251303136,-297360588],[1,-548350900,346769743],[1,-365405794,-181828913],[2,808605001],[2,-24985572],[1,-209873236,828628379],[1,-985899437,-373149465],[1,-142769390,479423308],[1,-589380987,-117054577],[2,142850111],[1,-466672220,-241367651],[2,292450586],[1,430370250,-51771885],[2,135812477],[1,-178726756,313410520],[1,-226167043,13946717],[1,195531397,267353165],[2,-248654947],[2,573927198],[1,-709998682,425791524],[2,-965801279],[2,-251946908],[2,89294557],[2,-599971081],[2,-387536461],[2,273842425],[1,-367756934,-672752222],[2,369396235],[2,264932273],[2,-389831860],[1,-119909016,-54220893],[1,173419117,-130298535],[2,493804611],[1,-152347275,-74440731],[1,165595518,143829987],[1,-770856215,-318712040],[1,-254977470,264119268],[2,-428948987],[2,-141340925],[1,-265922453,20474821],[2,283314865],[1,-483285733,-402452772],[2,265615928],[2,93035630],[1,-277291447,129358692],[2,337549273],[2,1028021228],[2,288981333],[1,66490022,852181964],[1,-88898622,426284554],[1,-572684156,-113568786],[1,-382066010,416480929],[1,-258787430,-523981204],[2,784651756],[1,-572286948,12092414],[1,265239807,-746877181],[2,-158504591],[1,-505803609,345817673],[1,-21147750,388530990],[1,636148060,-540170331],[1,-233811556,344334382],[1,496396505,625041],[1,145491545,-414799826],[1,124199127,-467912909],[2,229622351],[1,599060543,588326555],[2,571964160],[2,-16677395],[2,-127634926],[2,-655907508],[2,-975299348],[2,-347537925],[2,902677511],[1,-221985680,531581576],[2,268665745],[2,494209211],[1,-261794904,334838359],[1,-722632091,-128790912],[2,-576503043],[2,576856108],[2,-43471846],[1,-157653841,-76649508],[2,283492390],[1,-228714698,1188486],[2,110924049],[2,-75566603],[2,-48090170],[2,335701093],[2,431900251],[2,-967501590],[1,-626256297,339692461],[2,127928933],[1,213113548,-29912448],[2,-770856215],[2,647712400],[1,-209866510,593562910],[2,258190587],[2,-684722621],[2,-31346377],[2,712949831],[2,-752504350],[2,-32532816],[1,765054397,-148256640],[2,54543663],[1,-332588670,-172223193],[1,-774551516,-332570745],[2,832613060],[2,-470268949],[1,-207889004,-26395453],[2,16565143],[2,-650993502],[2,19202428],[1,509517420,66692250],[2,-63529672],[1,-48363343,-767283975],[2,-211304203],[1,-161221956,620841693],[2,-28610579],[2,452124022],[2,-78551401],[2,-469916810],[1,-164641736,-395799920],[2,-63196680],[1,167191421,-324231369],[1,-554857250,-976108099],[2,390520343],[1,944076772,-147469301],[2,407231551],[1,-437220314,-604898759],[1,981933680,-52857316],[2,225755901],[1,309253306,206460842],[1,-666268202,151927983],[2,901475284],[2,209216464],[2,-26838658],[1,416605113,-894051695],[1,162504308,89381094],[2,-91084058],[1,481599764,299392487],[2,-285905175],[1,369155349,336452379],[2,720825201],[2,-63307654],[2,-261091933],[2,-775496187],[2,-235687406],[2,420706286],[2,44239097],[1,95145162,-551778676],[1,590612439,658472968],[1,-357576425,-112363783],[1,-124992690,163005633],[1,-510882790,-4788163],[2,-321315990],[2,-115207402],[2,-127998354],[2,772886717],[2,-382066010],[1,-372805423,-14959900],[2,248069421],[2,-354857272],[2,173783545],[2,-543265267],[1,-427488045,389297122],[1,616430112,745577451],[1,411548724,-376434747],[2,-869925764],[2,-120495859],[2,19598838],[1,165396503,-508449596],[2,67763300],[1,-125486916,-198951213],[1,-45760568,270264774],[2,646348294],[1,288120405,-83502948],[1,-117813089,43071339],[1,140326633,19504603],[2,46270806],[2,436226154],[2,252047647],[2,-476866252],[1,-548530128,-31465053],[2,594155811],[2,658877397],[1,-229585536,-140087289],[2,681887563],[2,832613060],[2,-143089057],[1,846143632,185607679],[1,529252120,-406566626],[1,211559153,-481934815],[2,173419117],[2,24555938],[1,-77875388,759392121],[1,-812839232,-584085771],[2,1027104541],[2,-109388605],[1,-326989883,-116806210],[1,32369246,175035735],[2,-453992546],[1,-429493632,500469157],[2,38255525],[2,-476866252],[2,440399176],[1,-400835888,731947987],[1,907907998,-507012626],[2,-226474272],[1,783483666,-677851868],[2,-94049377],[1,-701687353,624581127],[1,335708648,-666857673],[2,-684343510],[1,769116862,-39246474],[1,-618606206,293819646],[2,142226979],[2,-783863055],[1,-462194152,-170274969],[2,964787205],[2,453681551],[2,-260198320],[1,168271058,559576270],[2,-19001637],[1,380140782,-309210363],[1,-132168268,1035356708],[2,739366],[2,-524618254],[2,-660132447],[2,-189347945],[1,-417283105,-169848020],[1,723238874,272783804],[2,22532879],[2,-994459042],[1,45984098,957234941],[2,-393119862],[1,488787225,-483645250],[2,762280777],[1,-176950163,213557593],[2,7763462],[1,-428886723,-34207585],[1,108522652,-675216308],[1,-439069931,-692651320],[2,-226167043],[2,-606726117],[2,297049086],[1,183084748,21546486],[2,-895823750],[1,320894943,1030558420],[1,455323909,238031536],[2,762909219],[2,-94140664],[2,112009198],[1,-45049014,-611671646],[1,-526362065,73455032],[2,396899955],[1,-395770170,546926611],[1,155625949,48673601],[1,118373832,-400788288],[2,-454349917],[1,373697337,144414179],[1,-447193112,-189597770],[2,-277291447],[2,-221985680],[1,-81492996,-538517795],[2,-2227629],[D1dDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD,418223624,446923989],[2,-78551401],[1,-449147056,542407845],[1,-687404389,-420860897],[2,-13837402],[2,-555245483],[1,-683160066,493782660],[2,52611943],[2,-313709513],[2,251360886],[1,112035297,-601612305],[2,-400835888],[2,433727551],[2,616523406],[2,-132034105],[1,-485627872,63857649],[1,-78912006,-187394377],[1,344524157,-876795500],[2,314779908],[1,19505670,305111957],[2,-716577145],[2,-412222919],[1,375540031,439278233],[2,-798455259],[2,496396505],[2,-188236722],[2,629047916],[1,-770943,-177170533],[1,-465588420,-343371211],[1,-669662245,-164667093],[1,301585080,145680611],[1,29588626,200899978],[2,825155456],[1,48896097,516712494],[2,138425152],[1,-268834242,-588921839],[2,-885254505],[2,-22680178],[1,-42408499,-431219283],[2,-194778332],[1,-538234567,329789052],[1,-727652262,-146627030],[2,351638993],[1,294620046,-764651166],[2,-105944431],[2,-314594975],[2,-669662245],[2,481599764],[1,-159569346,-566421162],[1,671015755,-84023304],[1,-558338080,-426562441],[1,295755905,-242830093],[1,160227475,710887764]],2");
        System.out.println(Arrays.deepToString(nums));
        Solution s = new Solution();
        int[] res = s.LRU(nums, 3);
        System.out.println(Arrays.toString(res));
    }
}
